/*
 * @Author: szx
 * @Date: 2022-06-09 12:49:22
 * @LastEditTime: 2022-06-09 14:08:39
 * @Description:
 * @FilePath: \leetcode\400-499\497\497.js
 */
/**
 * @param {number[][]} rects
 */
var Solution = function (rects) {
    this.rects = rects;
    this.sum = [0];
    for (const rect of rects) {
        const [x1, y1, x2, y2] = [...rect];
        this.sum.push(this.sum[this.sum.length - 1] + (x2 - x1 + 1) * (y2 - y1 + 1));
    }
};

/**
 * @return {number[]}
 */
Solution.prototype.pick = function () {
    let k = Math.floor(Math.random() * this.sum[this.sum.length - 1]);

    const rectIndex = binarySearch(this.sum, k + 1) - 1;
    k -= this.sum[rectIndex];
    const rect = this.rects[rectIndex];
    const [x1, y1, x2, y2] = [...rect];
    return [Math.floor(Math.random() * (x2 - x1 + 1) + x1), Math.floor(Math.random() * (y2 - y1 + 1) + y1)];
};

const binarySearch = (arr, target) => {
    let l = 0,
        r = arr.length - 1;
    while (l <= r) {
        const mid = (r + l) >> 1;
        const num = arr[mid];
        if (num === target) return mid;
        else if (num > target) r = mid - 1;
        else l = mid + 1;
    }
    return l;
};
/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(rects)
 * var param_1 = obj.pick()
 */
